package com.mjf.sort;

import java.util.Arrays;

/**
 * 归并排序
 * <p>
 * 思路：<br>
 * 归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之。
 * <p>
 * 先将元素分为一个一个元素，然后依次将相邻的元素合并为有序序列，详见doc中图解
 * <p>
 * 时间复杂度：O(nlogn)
 * <p>
 * 空间复杂度：O(n)
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {97, 65, 49, 38, 76, 13, 49, 27};
        int[] temp = new int[arr.length];
        System.out.println("排序前: " + Arrays.toString(arr));
        mergeSort(arr, 0, arr.length - 1, temp);
        System.out.println("排序后: " + Arrays.toString(arr));
    }

    /**
     * 归并排序
     *
     * @param arr   待排序数组
     * @param start 开始拆分的索引
     * @param end   结束拆分的索引
     * @param temp  中转数组
     */
    public static void mergeSort(int[] arr, int start, int end, int[] temp) {
        if (start < end) {
            int mid = (start + end) / 2;    // 中间索引
            // 向左进行拆分
            mergeSort(arr, start, mid, temp);
            // 向右进行拆分
            mergeSort(arr, mid + 1, end, temp);
            // 合并
            merge(arr, start, mid + 1, end, temp);
        }
    }

    /**
     * 将两个有序序列合并为一个有序序列
     *
     * @param arr        待排序数组
     * @param leftStart  左边有序序列的开始索引
     * @param rightStart 右边有序序列的开始索引（减一为左边有序序列的结束索引）
     * @param rightEnd   右边有序序列的结束索引
     * @param temp       中转数组
     */
    public static void merge(int[] arr, int leftStart, int rightStart, int rightEnd, int[] temp) {
        // 左边有序序列正在处理的索引
        int i = leftStart;
        // 右边有序序列正在处理的索引
        int j = rightStart;
        // 中转数组当前索引
        int t = 0;

        // 把左右两边有序序列的元素按照规则填充到temp, 直到有一边的有序序列处理结束为止
        while (i <= rightStart - 1 && j <= rightEnd) {
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                i++;
            } else {
                temp[t] = arr[j];
                j++;
            }
            t++;
        }

        // 将另一个没处理完的序列剩余元素依次写入temp
        while (i <= rightStart - 1 || j <= rightEnd) {
            if (i <= rightStart - 1) {
                temp[t] = arr[i];
                i++;
            } else {
                temp[t] = arr[j];
                j++;
            }
            t++;
        }

        // 将temp中的元素拷贝给arr
        t = 0;
        for (int k = leftStart; k <= rightEnd; k++, t++) {
            arr[k] = temp[t];
        }
//        System.out.println("本次合并后: " + Arrays.toString(arr));
    }
}
